package class08_greaterHeap;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
//加强堆
/*
* 可以根据值来删除、有从值到位置的索引
* */
//若是非基础类型，可以重复，否则不能重复
public class GreaterHeap<T> {
    private int heapSize;
    private ArrayList<T> heap;
    private HashMap<T,Integer> reverseIndexMap;
    private Comparator<? super T> comp;

    public GreaterHeap(Comparator<? super T> comp){
        this.heapSize = 0;
        this.heap = new ArrayList<T>();
        this.reverseIndexMap = new HashMap<T,Integer>();
        this.comp = comp;
    }

    public boolean isEmpty(){ return heapSize==0;}

    public int size(){return heapSize;}

    public Comparator<? super T> getComp() {
        return comp;
    }

    public T getElemByIndex(int index){
        return heap.get(index);
    }

    public boolean contains(T obj) {
        return reverseIndexMap.containsKey(obj);
    }

    public void push(T elem){
        heap.add(elem);
        this.reverseIndexMap.put(elem,heapSize++);//后++是因为索引比长度小1
        int index = heapSize-1;
        heapInsert(index);
    }

    public T pop() {
        swap(0,--heapSize);
        T temp = heap.get(heapSize);
        heap.remove(heapSize);
        reverseIndexMap.remove(temp);
        heapify(0);
        return temp;
    }

    public T peek() {
        return heap.get(0);
    }

    public void heapInsert(int index){
        int father = (index-1)/2;
        while(index>=0 && comp.compare(heap.get(father),heap.get(index))<0){
            swap(index,father);
            index = father;
            father = (index-1)/2;
        }
    }

    public void heapify(int index){
        int greaterChild = index*2+1;
        while(greaterChild<heapSize){
            if(index*2+2<heapSize &&
                    comp.compare(heap.get(greaterChild),heap.get(index*2+2))<0)
                greaterChild = index*2+2;
            if(comp.compare(heap.get(greaterChild),heap.get(index))>0){
                swap(greaterChild,index);
            }else{break;}
            index=greaterChild;
            greaterChild = index*2+1;
        }
    }

    public void removeByValue(T elem){
        T replace = heap.get(heapSize-1);
        int removedIndex = reverseIndexMap.get(elem);
        swap(reverseIndexMap.get(elem),heapSize-1);
        heap.remove(--heapSize);
        reverseIndexMap.remove(elem);
        if(elem!=replace){
            resign(replace);
        }
    }

    public ArrayList<T> getHeap(){
        return heap;
    }

    public void resign(T elem){
        heapInsert(reverseIndexMap.get(elem));
        heapify(reverseIndexMap.get(elem));
    }

    public void swap(int index1, int index2){
        T o1 = this.heap.get(index1);
        T o2 = this.heap.get(index2);

        //替换位置
        this.heap.set(index1,o2);
        this.heap.set(index2,o1);

        //更新反向索引表
        this.reverseIndexMap.put(o2,index1);
        this.reverseIndexMap.put(o1,index2);
    }
}
